/*
  注意在线OJ算法题分为两种类型：
 1. 接口类型OJ：此种OJ题目是方法名字已经给好，用户直接写代码即可，也不需要包含什么包
 2. IO类型的OJ：此种OJ题目需要用户定义一个public的Main类，然后在Main类中提供一个main方法，在main方法中完成事情，中间如要需要用到其他集合类，必须手动
    导入包
   在线OJ中的循环输入，输入单个值怎么循环接收，整行值怎么循环接收﻿
解题思路：
   参考课堂将的二叉树的创建以及遍历
*/
import java.util.*;
public class Main{
    // 二叉树的节点进行定义
    public static class TreeNode{
        char value;
        TreeNode left;
        TreeNode right;
        public TreeNode( char value){
            this.value = value;
        }
    }
    // 指向二叉树的根节点
    TreeNode root;
    int index;
    void createBinaryTree(String preStr, char invalid){
        index = 0;
        root = createBinaryTreeN(preStr, invalid);
    }
    TreeNode createBinaryTreeN(String preStr, char invalid){
        TreeNode treeRoot = null;
        if(index < preStr.length() && preStr.charAt(index) != invalid){
            // 创建根节点
            treeRoot = new TreeNode(preStr.charAt(index));
            // 创建根节点的左子树
            ++index;
            treeRoot.left = createBinaryTreeN(preStr, invalid);
            // 创建根节点的右子树
            ++index;
            treeRoot.right = createBinaryTreeN(preStr, invalid);
        }
        return treeRoot;
    }
    public void InOrder(){
        InOrder(root);
        System.out.println();
    }
    private void InOrder(TreeNode treeRoot){
        if(treeRoot != null){
            InOrder(treeRoot.left);
            System.out.print(treeRoot.value + " ");
            InOrder(treeRoot.right);
        }
    }
    public static void main(String[] args){
        Scanner scaner = new Scanner(System.in);
        while(scaner.hasNext()){
            // 接收前序遍历的结果
            String str = scaner.nextLine();
            Main tree = new Main();
            tree.createBinaryTree(str, '#');
            tree.InOrder();
        }
    }
}